Generally, comparison between two pieces of data is frequently performed in operations utilizing a computer. For example, sorting, in which a large number of data are rearranged, has been conventionally conducted by software. On the other hand, a circuit is known, which makes use of hardware at high speed two pieces of data.
FIG. 17 is a circuit diagram of a cell circuit 10 shown in Patent Laying-Open 62-118434 which is capable of storing and comparing 1 bit data. The cell circuit 10 comprises an SRAM section 50, transistors 56, 71, and 72 and a NAND gate 73. Data D, D are applied through a bit line pair BL, BL and comparison is made between data M, M stored in the SRAM section 50 and the applied data D, D. If the two data match, the NAND gate 73 generates a high level signal. This results in turning on the transistor 56. On the other hand, if the relation of the two pieces of data is M&lt;D, the transistors 71 and 72 are turned on thereby causing a comparison line CML to attain a low level. On the contrary, if the relation of the two data follows M&gt;D, the potential of the comparison line CML remains the same.
In order to compare two pieces of data each including a plurality of bits, it is necessary to connect a plurality of cell circuits 10 through the comparison line CML as shown in FIG. 18. A transistor T.sub.7 and an inverter INV are provided to transmit the comparison result quickly. This is because the transistor 56 for transmission in the cell circuit 10 is a passive device and the transmission of the comparison result is therefore delayed.
When a plurality of the cell circuits 10 are connected through the comparison line CML, the transistors 56 for transmitting comparison results are connected in series as shown in FIG. 19A. The equivalent circuit is shown in FIG. 19A. The series connection of the transistors 56 constitutes a delay circuit formed of resistance component R and capacitance component C shown in FIG. 19B. This means that a signal representative of a comparison result is inevitably delayed in the circuit connection indicated in FIG. 18. The signal indicating a comparison result is delayed most when the comparison result of two pieces of data is determined depending upon the comparison result at the least significant bit (LSB). That is, in this case, the signal representative of the comparison result in the cell circuit 10 which forms the LSB is transmitted toward the cell circuit of the most significant bit (MSB) through the comparison line CML. This results in a long period of time until the comparison result of the two pieces of data is generated. It is pointed out that a conventional comparison circuit shown in FIG. 18 has a low operating speed.
The Translation Lookaside Buffer (referred to as "TLB" hereinafter), to which the present invention may be applied, will be described below. Generally, in addressing a memory in a computer system, translation is conducted from a logical address (or a virtual address) into a physical address. In the translation, it is usually required to refer to a segment map table or a page map table etc. on the main memory. This means that it is necessary to make an access to the main memory at least three times in order that one instruction is executed by the computer. To increase the processing speed by the computer, it is necessary to reduce the number of the accesses. The TLB is known as a register capable of translating a logical address into a physical address without referring to the map table on the main memory. An example of a microprocessor provided with the TLB is found, for instance, in an article under the title of "A 32-bit CMOS Microprocessor with On-chip Cache and TLB" (IEEE Journal of Solid-State Circuits VOL. SC-22, NO. 5, October, 1987) While several kinds of TLB have been conventionally known, a TLB for the full associative method, to which the present invention is applicable, will be described below. Now, in the following, a logical space of 4 giga bytes which can be designated by an address signal of 32 bits is assumed. In the logical space, data of 512 bytes which can be designated by an address signal of 9 bits is defined as 1 page. As seen from FIG. 9, the logical address comprises a page address and an offset address.
A conceptual structure of the TLB is shown in FIG. 10.
The TLB in accordance with the full associative method generally comprises a CAM section 71 for storing a logical page address and an SRAM section 72 for storing a physical page address. Each of the CAM section 71 and SRAM section 72 comprises the address storage locations of 32 entries, respectively. In operation, when a logical page address is applied to the CAM section 71, the location in which an address identical to the applied logical page address is stored, i.e. the word is detected. The detection of the match is performed by comparing the two logical page addresses, and is called "hit". The physical page address is generated from the SRAM section 72 corresponding to the hit word. If a certain word is hit in the CAM section 71, the translation from the logical page address into the physical page address therefor can be completed during 1 machine cycle.
On the other hand, if a match is not detected in the CAM section 71, i.e. a logical page address is not hit, the segment map table or page map table etc. is referred to, whereby the physical page address is obtained. The obtained physical page address is required to be registered in the CAM section 71 and SRAM section 72 for the processing thereafter. For the registration, it is necessary to delete the data of at least one word previously registered in the TLB, and to write new data in the word-deleted storage location. As a kind of algorithm to determine the word to be deleted or the storage location of the word to be deleted, the "Least Recently Used" algorithm (referred to as "LRU" hereinafter) is known. In order to implement the algorithm of LRU, it is further necessary to provide a counter for each word.
FIG. 11 is a conceptual diagram describing how data in the TLB is updated in accordance with the LRU algorithm. Referring to FIG. 11, a counter is provided for each entry or each word in the TLB 70, thus forming a counter section 73. If an applied logical page address hits a certain entry in the TLB 70, the counter of an entry having a counter value smaller than the counter value of the above mentioned entry is incremented. At the same time, the counter of the hit entry is reset. If an applied logical page address does not hit any entry in the TLB 70 (in case of mis-hitting), the data of the entry having the largest counter value is deleted, and new data is written therein. FIG. 11 shows the value of an entry having a counter value of 15 is deleted, and new data is written therein.
As mentioned above, in the CAM section 71 shown in FIG. 10 or 11, two pieces of data having a plurality of bits are compared. In the comparison, it is pointed out that the delays shown in FIGS. 18, 19A, and 19B take place, preventing high speed translation from the logical address into the physical address as a result.